#include <cstdio>

int n, m, a[ 1001 ], f[ 1001 ][ 1001 ], v[ 1001 ][ 1001 ], sum[ 1001 ];

void init( )
{
    int i, j, t = 0;
    for ( i = 0; i < n; i++ )
    {
        scanf("%d", &a[ i ]);
        t += a[ i ];
        sum[ i ] = t;
    }
    for ( i = n - 1; i >= 0; i-- )
    {
        v[ i ][ i ] = 0;
        for ( j = i + 1; j < n; j++ )
            v[ i ][ j ] = v[ i + 1 ][ j ] + a[ i ] * ( sum[ j ] - sum[ i ] );
    }
}

void work( )
{
    int i, j, k, minn, left, right, x, y;
    for ( i = 0; i < n; i++ )
    {
        f[ i ][ 0 ] = v[ 0 ][ i ];
        for ( j = 1; j < i && j <= m; j++ )
        {
            minn = 0xfffffff;
            left = j - 1;
            right = i - 1;
            while ( left + 5 < right )
            {
                x = left + ( right - left ) / 3;
                y = left + ( right - left ) * 2 / 3;
                if ( f[ x ][ j - 1 ] + v[ x + 1 ][ i ] < f[ y ][ j - 1 ] + v[ y + 1 ][ i ] )
                    right = y;
                if ( f[ x ][ j - 1 ] + v[ x + 1 ][ i ] > f[ y ][ j - 1 ] + v[ y + 1 ][ i ] )
                    left = x;
                if ( f[ x ][ j - 1 ] + v[ x + 1 ][ i ] == f[ y ][ j - 1 ] + v[ y + 1 ][ i ] )
                {
                    left = x;
                    right = y;
                }
            }
            for ( k = left; k <= right; k++ )
                if ( minn > f[ k ][ j - 1 ] + v[ k + 1 ][ i ] )
                    minn = f[ k ][ j - 1 ] + v[ k + 1 ][ i ];
            f[ i ][ j ] = minn;
        }
    }
    printf("%d\n", f[ n - 1 ][ m ]);
}

int main( )
{
    while ( scanf("%d%d", &n, &m) )
    {
        if ( n == 0 && m == 0 )
            break;
        init( );
        work( );
    }
    return 0;
}
